// OK, let's try all this using Java-style iterators.  From what
// I recall, such iterators use pointers instead of values.
// They can have memory leaks, though, because they are allocated
// on the heap.

#include <list>
#include <vector>
#include <iostream>

//-----------------------------------------------------------------
template <class E>
class Iterator {
public:
    virtual bool has_next() = 0;
    virtual E get_next() = 0;
    virtual ~Iterator() {}
};

//-----------------------------------------------------------------
template <class E>
class Iterator_List : public Iterator<E> {
private:
    typename std::list<E>::iterator begin;
    typename std::list<E>::iterator end;
    typename std::list<E>::iterator next;

public:
    Iterator_List(typename std::list<E>::iterator begin,
                  typename std::list<E>::iterator end);
    bool has_next();
    E get_next();
};

template<class E>
Iterator_List<E>::Iterator_List(typename std::list<E>::iterator begin,
                                typename std::list<E>::iterator end) {
    this->begin = begin;
    this->end = end;
    next = begin;
}

template<class E>
bool Iterator_List<E>::has_next() {
    return next != end;
}

template<class E>
E Iterator_List<E>::get_next() {
    return *next++;
}

//-----------------------------------------------------------------
template <class E>
class Iterator_Vector : public Iterator<E> {
private:
    typename std::vector<E>::iterator begin;
    typename std::vector<E>::iterator end;
    typename std::vector<E>::iterator next;

public:
    Iterator_Vector(typename std::vector<E>::iterator begin,
                    typename std::vector<E>::iterator end);
    bool has_next();
    E get_next();
};

template<class E>
Iterator_Vector<E>::Iterator_Vector(typename std::vector<E>::iterator begin,
                                    typename std::vector<E>::iterator end) {
    this->begin = begin;
    this->end = end;
    next = begin;
}

template<class E>
bool Iterator_Vector<E>::has_next() {
    return next != end;
}

template<class E>
E Iterator_Vector<E>::get_next() {
    return *next++;
}

//-----------------------------------------------------------------
template<class E>
class Collection {
public:
    virtual ~Collection() {}
    virtual Iterator<E> *get_iterator() = 0;
    virtual void add(E x) = 0;

    void print();
};

template<class E>
void Collection<E>::print() {
    Iterator<E> *iter = get_iterator();
    while (iter->has_next())
        std::cout << iter->get_next() << " ";
    std::cout << "\n";
    delete iter;
}

//-----------------------------------------------------------------
template<class E>
class Collection_List : public Collection<E> {
public:
    Iterator<E> *get_iterator();
    void add(E x);

private:
    std::list<E> items;
};


template<class E>
Iterator<E> *Collection_List<E>::get_iterator() {
    return new Iterator_List<E>(items.begin(), items.end());
}

template<class E>
void Collection_List<E>::add(E x) {
    items.push_back(x);
}

//-----------------------------------------------------------------
template<class E>
class Collection_Vector : public Collection<E> {
public:
    Iterator<E> *get_iterator();
    void add(E x);

private:
    std::vector<E> items;
};


template<class E>
Iterator<E> *Collection_Vector<E>::get_iterator() {
    return new Iterator_Vector<E>(items.begin(), items.end());
}

template<class E>
void Collection_Vector<E>::add(E x) {
    items.push_back(x);
}

int main() {
    Collection_List<int> lis;

    lis.add(1);
    lis.add(2);
    lis.add(3);

    Iterator<int> *iter = lis.get_iterator();
    while (iter->has_next())
        std::cout << iter->get_next() << " ";
    std::cout << "\n";
    delete iter;

    lis.print();

    Collection_Vector<int> vec;

    vec.add(4);
    vec.add(5);
    vec.add(6);

    iter = vec.get_iterator();
    while (iter->has_next())
        std::cout << iter->get_next() << " ";
    std::cout << "\n";
    delete iter;

    vec.print();
}

